//https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
package codeRandomThoughts.Test28找出字符串中第一个匹配项的下标;

public class Solution4 {
    public int strStr(String haystack, String needle) {
        char[] p = needle.toCharArray();
        char[] str = haystack.toCharArray();
        int[] next = getNextFromPattern(needle);

        //定义两个指针
        //一个指向主串
        int i = -1;
        //一个指向模式串
        int j = -1;

        for (; i < str.length - 1; i++) {
            while (j > -1 && str[i + 1] != p[j + 1]) {
                j = next[j];
            }
            if (str[i + 1] == p[j + 1]) {
                j++;
            }
            //说明j已经匹配到了模式串的末尾,说明全部能对应上
            if (j == p.length - 1) {
                return i + 1 - j;
            }
        }
        return -1;
    }

    //next数组属于准备工作
    public int[] getNextFromPattern(String needle) {
        char[] pattern = needle.toCharArray();

        //前缀末尾指向的位置
        int prefixEnd = 0;
        //后缀末尾指向的位置
        int postfixEnd = 0;

        //next[0] = -1
        //next数组记录的是以当前位置i为结尾的模式串子串的最长前后缀
        int[] next = new int[pattern.length];
        next[0] = -1;

        for (int i = 0; i < next.length - 1; i++) {
            prefixEnd = next[i];
            postfixEnd = i;

            //匹配不成功就一直回退,最多退回-1
            while (prefixEnd > -1 && pattern[prefixEnd + 1] != pattern[postfixEnd + 1]) {
                prefixEnd = next[prefixEnd];
            }

            if (pattern[prefixEnd + 1] == pattern[postfixEnd + 1]) {
                //next[i + 1] = next[i] + 1;
                //上面是错的 因为我们要按照回退过后的位置来计算公共前后缀长度
                next[i + 1] = prefixEnd + 1;
            } else {
                //匹配不上就是-1
                next[i + 1] = -1;
            }
        }

        return next;
    }
}
